//There is an integer array nums sorted in non-decreasing order (not necessarily
// with distinct values). 
//
// Before being passed to your function, nums is rotated at an unknown pivot ind
//ex k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1]
//, ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0
//,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,
//2,4,4]. 
//
// Given the array nums after the rotation and an integer target, return true if
// target is in nums, or false if it is not in nums. 
//
// You must decrease the overall operation steps as much as possible. 
//
// 
// Example 1: 
// Input: nums = [2,5,6,0,0,1,2], target = 0
//Output: true
// Example 2: 
// Input: nums = [2,5,6,0,0,1,2], target = 3
//Output: false
// 
// 
// Constraints: 
//
// 
// 1 <= nums.length <= 5000 
// -104 <= nums[i] <= 104 
// nums is guaranteed to be rotated at some pivot. 
// -104 <= target <= 104 
// 
//
// 
// Follow up: This problem is similar to Search in Rotated Sorted Array, but num
//s may contain duplicates. Would this affect the runtime complexity? How and why?
// 
// Related Topics 数组 二分查找 
// 👍 441 👎 0


package leetcode.editor.cn;

//Java：Search in Rotated Sorted Array II
class P81SearchInRotatedSortedArrayIi {
    public static void main(String[] args) {
        Solution solution = new P81SearchInRotatedSortedArrayIi().new Solution();
        // TO TEST
        System.out.println(solution.search(new int[]{1, 0, 1, 1, 1}, 0));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean search(int[] nums, int target) {
            int left = 0;
            int right = nums.length - 1;
            int len = right;

            while (left <= right) {
                int mid = (left + right) / 2;
                if (nums[mid] == target || nums[left] == target || nums[right] == target) return true;
                if (nums[mid] > nums[len]) {
                    // 二分查找应该在有序数组中进行，此时[left, mid)有序
                    if (target >= nums[left] && target < nums[mid]) {
                        // 如果在[left, mid)区间，则应该继续在[left, mid - 1)中继续查找
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                } else {
                    // 二分查找应该在有序数组中进行，此时(mid, right]有序
                    if (target > nums[mid] && target <= nums[right]) {
                        // 如果在(mid, right]区间，则应该继续在(mid + 1, right]中继续查找
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
            }
            return false;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}